/*
 * @lc app=leetcode.cn id=1921 lang=cpp
 *
 * [1921] 消灭怪物的最大数量
 */

// @lc code=start
class Solution {
public:
    // 1 3 4  1 1 1
    // 1 1 2 3   1 1 1 1 
    // 1
    // 3 2 4    5 3 2
    // 3, 2 

    // dist 到城市的初始距离
    // speed 怪物的移动速度
    // 一分钟杀掉一个怪物,  在输掉游戏之前杀尽可能多的怪物, 最多杀多少
    int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
        // 优先杀到达时间为最短
        int n {0};
        vector<int> arrivalTime(dist.size());

        for(int i = 0; i < dist.size(); ++i)
        {
            // 到达时间
           arrivalTime[i] = dist[i] / speed[i] + ((dist[i] % speed[i] > 0) ? 1 : 0);
        }

        sort (arrivalTime.begin(), arrivalTime.end());

        for(int i = 0; i < arrivalTime.size(); ++i)
        {
            // 怪物闯入城市
            if(arrivalTime[i] <= i)
            {
                return i;
            }
        }

        // 否则杀干净了
        return dist.size();
    }
};
// @lc code=end

